Explosive growth in embedded computing and rapid advances in low power wireless networking technologies are fueling the development of wireless sensor networks. These dynamic and adaptive distributed systems have applications ranging from wildlife habitat monitoring, inventory management, data collection and military and space applications.
Sensor networks are composed of low-power sensor nodes capable of sensing particular physical phenomena and communicating among themselves using wireless transceivers. The nodes are usually powered by batteries. Due to the large number of nodes, their low cost, and the amount of time they are expected to be deployed in a potentially inaccessible area (without provision for recharging the batteries), energy-efficiency becomes perhaps the most important design criteria for sensor networking protocols.
Under the traditional energy model, a static sensor network can be represented by a set of nodes V with each sensor node possessing a geographical position attribute. The transmission energy, Euvxmit, required to transmit a bit of data from a node u to a node v over the wireless channel is dependent upon the RF propagation path loss suffered over the distance du, between them:Euvxmit=Etx-elect+εampduvα; α=2  (1)where α is the path loss exponent and is dependent on the propagation channel and environmental conditions; Etx-elec is the energy expenditure in the transmitter electronics (per bit); and εamp is a constant that is characteristic of the amplifier in the transmitter.
The reception energy Euvrcv required to receive a bit of data at the receiver is simply the energy expenditure in the receiver electronics (per bit):Euvrcv=Erx-elec  (2)
A majority of sensor applications involve data gathering and dissemination; hence, energy efficient mechanisms for providing these services become critical.
In data dissemination (or broadcasting), a transmission from one node is propagated throughout the network by the other sensor transceivers. In order to consume the minimum amount of energy for broadcasting a bit of data to all nodes in the network, it is necessary to minimize both the number and energy of these transmissions. Dissemination in wireless networks is distinguished from dissemination in the point-to-point counterpart because wireless channels have inherent broadcast capability. Wieselthier et al. coined the term “wireless multicast advantage” (WMA) for this phenomenon and developed energy-efficient protocols which exploit the WMA. See J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, “On the Construction of Energy-efficient Broadcast and Multicast Trees in Wireless Networks,” Proc. IEEE INFOCOM, pp. 585-594, Tel Aviv, Israel, March 2000, which is hereby incorporated by reference in its entirety.
In data gathering, sensor networks can be classified into two categories: (1) query-driven and (2) event-driven. For the query-driven case, a user submits a query from a base station node which is then propagated through the network by the sensor transceivers. Sensors that can satisfy the query respond to the originator by means of unicast communications which are propagated back to the base station in the same manner. In an event-driven system, each sensor sends data to the base station whenever it detects a certain event. This triggered mechanism can be thought of as a response to a longstanding query about that event.
Since sending data along individual unicast paths from multiple sensors to the base station is costly in terms of energy expenditure, researchers have proposed mechanisms to aggregate upstream data as it propagates through the network. Essentially, the sensed data flows back to the base station along the edges of a spanning tree which is constructed during the query dissemination phase. Such trees are referred to as routing trees or gradients. In this context, the principal mechanism of energy minimization is the suppression of redundant data packets in the network. See S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong, “TAG: a Tiny Aggregation Service for Ad-Hoc Sensor Networks,” Proc. Symposium on Operating Systems Design and Implementation (OSDI), December 2002; and J. Zhao, R. Govindan, and D. Estrin, “Computing Aggregates for Monitoring Wireless Sensor Networks,” Proc. IEEE International Workshop on Sensor Network Protocols and Applications, Anchorage, Ak., May 2003, both of which are hereby incorporated by reference in their entirety. Data fusion and decision fusion techniques combine aggregation mechanisms with in-network processing of sensor data in order to further conserve energy.
The ability to modify transmit power in sensors provides another powerful tool for minimizing energy in both data gathering and dissemination and is a feature of numerous new sensor systems, such as the ARL sensor radio. See R. Tobin, “US Army's BLUE Radio,” Proc. SPIE, Unattended Ground Sensor Technologies and Applications V, volume 5090, Orlando, Fla., April 2003, which is hereby incorporated by reference in its entirety. With such techniques, each node has the ability to control its transmit power (either arbitrarily or discretely) so that it may control the reach of its broadcast, and thus control how many neighboring nodes are able to receive it.
If arbitrary transmission power control is considered in the traditional energy model, every pair of nodes in the network will have an edge connecting them and the total energy cost, Euv, of a bit transmitted along that edge is computed to be the cost due to wireless transmission over a certain distance plus the cost due to reception by the destination radio hardware:
                                                                        E                uv                            =                                                E                  uv                  xmit                                +                                  E                  uv                  rcv                                                                                                                        =                                                      E                                          rx                      -                      elec                                                        +                                      E                                          tx                      -                      elec                                                        +                                                            ɛ                      amp                                        ⁢                                          d                      uv                      α                                                                                  ;                              α                ≥                2                                                                        (        3        )            
The energy costs in the traditional model are symmetric, i.e., Euv=Evu. Hence, in order to transmit a bit of data from all sensors to a base station node, it was considered to be energy efficient to send and aggregate the data along the edges of an undirected Minimum Energy Spanning Tree (MEST) calculated on the entire network graph.
In the traditional model, the network is represented as a complete graph (“clique”) under the assumption of arbitrary power control. If the peak transmission power is fixed and the transmitter is allowed to transmit at discrete power levels only, then the resulting graph may not be a clique, but the edge costs are nevertheless easy to formulate. Once the costs are known, Kruskal's or Prim's algorithm could be used to calculate the undirected MEST in O(e log n) time. See T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms. MIT Press and McGraw-Hill, 1990, which is hereby incorporated by reference in its entirety.
For cliques, a complexity of O(n2) could be achieved using efficient priority queue data structures. Each leaf node in the resulting MEST transmits its data to its parent which aggregates this data with its own and that of other children nodes before transmitting the aggregate to its own parent node. This process continues until the base station receives the complete set of aggregates from its children.
Researchers routinely use the above energy model for modeling energy costs of edges in the network graph. However, the traditional model is inadequate for dense sensor networks. Due to the broadcast nature of the wireless channel, nodes in the vicinity of a sender node overhear its packet transmissions even if they are not an intended recipient. When a certain node u transmits a data packet for node v using optimal transmission power, all nodes x such that the distance dux<duv also receive (or overhear) the packet unnecessarily. To illustrate, when node 3 in FIG. 1A forwards its data packet to node 6, its transmission is overheard by nodes 5, 7 and 9. This redundant reception results in unnecessary expenditure of battery energy by the unintended recipients. Hence, the reception energy costs increase. This is especially true for dense networks where each node has several neighbors in close proximity.
Since idle listening on a wireless channel is a significant source of energy consumption, researchers have proposed a multitude of schemes for mitigating this problem. Preamble sampling, Power Aware Multi-Access Protocol with Signaling (PAMAS), and wake-on-wireless are representative of such schemes.
In preamble sampling schemes, a sensor node goes into fine-grained periods of sleep and wakes up periodically to sample the channel, and it remains awake if it sees a preamble transmitted by the sender. However, the receiver may still incur the overhearing energy cost since it must decode the entire packet before ascertaining whether it indeed is an intended recipient of the transmission.
Both PAMAS and wake-on-wireless schemes separate the signaling and data channels to achieve greater power efficiency. In wake-on-wireless, a low-power radio listens to incoming transmissions and wakes up the main radio when it detects a valid incoming packet. Although this technique mitigates the overhearing energy cost in point-to-point transmissions (as in the data gathering case), it is ineffective in the network-wide data dissemination scenario. This is because the low-power radio will always wake up the main radio upon the arrival of a broadcast packet, even if that packet is redundant from a dissemination standpoint. The energy cost of a complete packet reception is greater than the cost of remaining idle and is compounded by the need of the receiver to decode the entire packet before determining whether it is the intended recipient. This can add significant costs to dense sensor networks where a given packet transmission can be overheard by a large number of receivers.
Turning off neighboring radios during a certain point-to-point wireless transmission can mitigate overhearing costs. However, such fine grained scheduling of receiver electronics comes at a high price in terms of hardware complexity and may induce delays in protocol processing at higher layers.
Therefore, there is a need for systems, methods and computer readable media for systematically minimizing the impact of energy cost due to overhearing during data gathering and dissemination.